package com.celan.year2023.month05.day15;

import java.util.Stack;

/**
 * @author Celan
 * @description TODO
 */
class Solution {
    public String removeDuplicateLetters(String s) {
        //单调栈
        Stack<Character> stack = new Stack<>();
        //cnt记录字母出现次数
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) cnt[c - 'a']++;
        //vis记录是否访问过
        boolean[] vis = new boolean[26];

        for (char c : s.toCharArray()) {
            cnt[c - 'a']--;
            if (vis[c - 'a']) continue;
            //若栈顶元素比c大 => 应该排在后面
            while (!stack.empty() && stack.peek() > c) {
                //查看栈顶元素后面还有没有
                // => 有则弹出 vis[] 置 false
                // => 没有则不弹出
                if (cnt[stack.peek() - 'a'] == 0) break;
                vis[stack.pop() - 'a'] = false;
            }
            //将 c 压入栈
            stack.push(c);
            vis[c - 'a'] = true;
        }

        StringBuilder sb = new StringBuilder();
        while (!stack.empty()) sb.append(stack.pop());

        return sb.reverse().toString();
    }
}
